#include <iostream>
#include <queue>
using namespace std;


//https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool Find(TreeNode* root, TreeNode* ret, queue<TreeNode*>& s) {
        if (root == nullptr) {
            return false;
        }
        if (root == ret) {
            s.push(root);
            return true;
        }
        if (Find(root->left, ret, s)) {
            s.push(root);
            return true;
        }
        if (Find(root->right, ret, s)) {
            s.push(root);
            return true;
        }
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* cur = root;
        queue<TreeNode*> sp;
        queue<TreeNode*> sq;
        Find(root, p, sp);
        Find(root, q, sq);
        while (sp.size() > sq.size()) {
            sp.pop();
        }
        while (sq.size() > sp.size()) {
            sq.pop();
        }
        while (1) {
            if (sp.front() == sq.front()) {
                return sp.front();
            }
            sp.pop();
            sq.pop();
        }
    }
};

int main() {

    return 0;
}